package org.nowcoder.huawei.c200;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 45：计算三叉搜索树的高度
 */
public class HC045 {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode mid;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return String.valueOf(val);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];
        String[] vars = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(vars[i]);
        }
        TreeNode root = new TreeNode(nums[0]);
        buildTree(nums, root, 1);
        System.out.println(getHeight(root));
        System.out.println(root);
    }

    public static int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left); // 计算左子树的高度
        int midHeight = getHeight(root.mid); // 计算中间子树的高度
        int rightHeight = getHeight(root.right); // 计算右子树的高度
        return Math.max(Math.max(leftHeight, midHeight), rightHeight) + 1;
    }

    public static void buildTree(int[] nums, TreeNode root, int index) {
        if (index < nums.length) {
            TreeNode node = new TreeNode(nums[index]);
            TreeNode cur = root, pre = cur;
            while (cur != null) {
                pre = cur;
                if (nums[index] < cur.val - 500) {
                    cur = cur.left;
                } else if (nums[index] > cur.val + 500) {
                    cur = cur.right;
                } else {
                    cur = cur.mid;
                }
            }
            if (nums[index] < pre.val - 500) {
                pre.left = node;
            } else if (nums[index] > pre.val + 500) {
                pre.right = node;
            } else {
                pre.mid = node;
            }
            buildTree(nums, root, index + 1);
        }
    }
}
